#!/usr/bin/perl
use strict;
use warnings;
use constant {
    TOKEN_END_OF_STREAM => -1,
    TOKEN_NEWLINE => -2, # \n
    TOKEN_SEMI => ord(";"), # ;
    TOKEN_AMP => ord("&"), # &
    TOKEN_BAR => ord("|"), # |
    TOKEN_LESS => ord("<"), # <
    TOKEN_GREAT => ord(">"), # >
    TOKEN_LPAREN => ord("("), # (
    TOKEN_RPAREN => ord(")"), # )
    TOKEN_LBRACE => ord("{"), # {
    TOKEN_RBRACE => ord("}"), # }
    TOKEN_BANG => ord("!"), # !
    TOKEN_AND_IF => 128, # &&*
    TOKEN_OR_IF => 129, # ||*
    TOKEN_DSEMI => 130, # ;;*
    TOKEN_DLESS => 131, # <<*
    TOKEN_DGREAT => 132, # >>*
    TOKEN_LESSAND => 133, # <&*
    TOKEN_GREATAND => 134, # >&*
    TOKEN_LESSGREAT => 135, # <>*
    TOKEN_DLESSDASH => 136, # <<-*
    TOKEN_CLOBBER => 137, # >|*
    TOKEN_WORD => 138,
    TOKEN_NAME => 139, # not distinguish WORD and NAME right now
    TOKEN_ASSIGNMENT => 140, # = 
    TOKEN_IO_NUMBER => 141,
    TOKEN_IF => 142, # if*
    TOKEN_THEN => 143, # then*
    TOKEN_ELSE => 144, # else*
    TOKEN_ELIF => 145, # elif*
    TOKEN_FI => 146, # fi*
    TOKEN_DO => 147, # do*
    TOKEN_DONE => 148, # done*
    TOKEN_CASE => 149, # case*
    TOKEN_ESAC => 150, # esac*
    TOKEN_WHILE => 151, # while*
    TOKEN_UNTIL => 152, # until*
    TOKEN_FOR => 153, # for*
    TOKEN_IN => 154, # in*
    TOKEN_LFANG => 155, # [
    TOKEN_RFANG => 156, # ]
    BASE_CONTEXT => 0, 
    RULE_1_CONTEXT => 1,
    RULE_5_CONTEXT => 5,
    RULE_6_CONTEXT => 6,
    RULE_7a_CONTEXT => 7,
    RULE_7b_CONTEXT => 8,
    RULE_8_CONTEXT => 9,
    EOS => -1,
};

#require "scanner.pl";

open LOG, ">parser.log";

my @token_list;
my %token;
my $index = -1;
my $debug = 1;

sub change_type {
    my $new_type = shift;
    if ($token{tokenType} == TOKEN_WORD) {
        $token{tokenType} = int($new_type);
    }
}


sub get_tokens {
    open FIN, "<tokens.tk";
    my %token;
    while (1) {
        my $tokenType = <FIN>; chomp $tokenType;
        my $tokenText;
        while (1) {
            my $tmp = <FIN>;
            chomp $tmp;
            last if ($tmp=~/========/);
            $tokenText .= $tmp;
        }
        my %token = (
            tokenType => int($tokenType),
            text => $tokenText,
            );
        push @token_list, \%token;
        if (int($tokenType) == TOKEN_END_OF_STREAM) {
            last;
        }
    }
}

sub getText {
    return $token{text};
}

sub getType {
    return $token{tokenType};
}

sub match { 
    my $type = shift;
    # my $tmp_index = $index;
    # if ($type != TOKEN_NEWLINE) {
    #     my %tmp_token = %{$token_list[$tmp_index]};
    #     while ($tmp_token{tokenType} == TOKEN_NEWLINE) {
    #         $tmp_index++;
    #         %tmp_token = %{$token_list[$tmp_index]};
    #     }
    #     if ($tmp_token{tokenType} == $type) {
    #         $index = $tmp_index;
    #         %token = %tmp_token;
    #     }
    # }
    return $token{tokenType} == $type;
}

sub advance {
    $index++;
    %token = %{$token_list[$index]};
    print LOG "=====[next] $token{text} [type] $token{tokenType}\n";
}

sub back_step {
    $index--;
    %token = $token_list[$index];
}

sub skipLinebreaks {
    while (match(TOKEN_NEWLINE)) {
        advance();
    }
    print LOG "skip[next] $token{text} [type] $token{tokenType}\n";
}


# complete_command : list separator
#                  | list
#                  ;
sub parse {
    if ($debug) {
        print LOG "parse()\n";
    }
    advance();
    skipLinebreaks();
    while (!match(TOKEN_END_OF_STREAM)) {
        print "\nsuspend in parser()";
        # my $suspend = <STDIN>;
        list();
        # advance();
        skipLinebreaks();
    }
    if ($debug) {
        print LOG "[end] got the TOKEN_END_OF_STREAM\n";
    }
}

# list             : list separator_op and_or
#                  |                   and_or
#                  ;
# list             :              and_or list_R
# list_R           | separator_op and_or list_R
#                  | /* empty */
sub list {
    if ($debug) {
        print LOG "list()\n";
    }
    my $ret = and_or();
    my $loop = 1;
    my @rets;
    while (defined($ret)) {
        push @rets, $ret;
        print "\nsuspend in list()";
        # my $suspend = <STDIN>;
        if (match(TOKEN_SEMI)){
            if ($debug) {
                print LOG "[match] TOKEN_SEMI\n";
            }
            advance();
            # do
        }
        elsif (match(TOKEN_AMP)) {
            if ($debug) {
                print LOG "[match] TOKEN_AMP\n";
            }
            advance();
            # do
        }
        elsif (match(TOKEN_NEWLINE) || match(TOKEN_END_OF_STREAM)) {
            if ($debug) {
                print LOG "[match] TOKEN_NEWLINE or TOKEN_END_OF_STREAM\n";
            }
            last;
        }
        else {
            die "Missmatched in list(), got type: ". getType(). " text: ".getText()."\n";
            # exception
        }
        $ret = and_or_opt();
    }
    if ($debug) {
        print LOG "return list()\n";
    }
    return @rets;
}

# and_or           :                         pipeline
#                  | and_or AND_IF linebreak pipeline
#                  | and_or OR_IF  linebreak pipeline
#                  ;
# and_or           :                  pipeline and_or_R
# and_or_R         | AND_IF linebreak pipeline and_or_R
#                  | OR_IF  linebreak pipeline and_or_R
#                  | /* empty */
sub and_or {
    if ($debug) {
        print LOG "and_or()\n";
    }
    my @ret;
    while (1) {
        print "\nsuspend in and_or()";
        # my $suspend = <STDIN>;
        my $pl = pipeline();
        if (match(TOKEN_AND_IF)) {
            if ($debug) {
                print LOG "[match] TOKEN_AND_IF\n";
            }
            advance();
            # do
        }
        elsif (match(TOKEN_OR_IF)) {
            if ($debug) {
                print LOG "[match] TOKEN_OR_IF\n";
            }
            advance();
            # do
        }
        else {
            # /* empty */
            push @ret, $pl;
            last;
        }
        push @ret, $pl;
        # skipLinebreaks();
    }
    if ($debug) {
        print LOG "return and_or()\n";
    }
    return @ret;
}

sub and_or_opt {
    if ($debug) {
        print LOG "and_or_opt()\n";
    }
    if (match(TOKEN_LBRACE) || match(TOKEN_LPAREN) 
            || match(TOKEN_WORD) || match(TOKEN_IF)
            || match(TOKEN_WHILE) || match(TOKEN_UNTIL)
            || match(TOKEN_CASE) || match(TOKEN_FOR)
            || match(TOKEN_IO_NUMBER) || match(TOKEN_LESS)
            || match(TOKEN_GREAT) || match(TOKEN_DLESS)
            || match(TOKEN_DGREAT) || match(TOKEN_LESSAND)
            || match(TOKEN_GREATAND) || match(TOKEN_LESSGREAT)
            || match(TOKEN_CLOBBER) || match(TOKEN_ASSIGNMENT)) {
        if ($debug) {
            print LOG "[next token] *".getType()."\n";
        }
        my $and_or = and_or();
        if ($debug) {
            print LOG "return and_or_opt()\n";
        }
        return $and_or;
    }
    else {
        if ($debug) {
            print LOG "return and_or_opt()\n";
        }
        return undef;
    }
}

# pipeline         :      pipe_sequence
#                  | Bang pipe_sequence
#                  ;
sub pipeline {
    if ($debug) {
        print LOG "pipeline()\n";
    }
    if (match(TOKEN_LFANG)) {
        if ($debug) {
            print LOG "[match] TOKEN_LFANG\n";
        }
        advance();
    }
    if (match(TOKEN_BANG)) {
        if ($debug) {
            print LOG "[match] TOKEN_BANG\n";
        }
        advance();
    }
    
    my @ret = pipe_sequence();
    if (match(TOKEN_RFANG)) {
        if ($debug) {
            print LOG "[match] TOKEN_RFANG\n";
        }
        advance();
    }
    if ($debug) {
        print LOG "return pipeline()\n";
    }
    return @ret;
}

# pipe_sequence    :                             command
#                  | pipe_sequence '|' linebreak command
#                  ;
sub pipe_sequence {
    if ($debug) {
        print LOG "pipe_sequence()\n";
    }
    my @commands = command();
    while (match(TOKEN_BAR)) {
        print "\nsuspend in pipe_sequence()";
        # my $suspend = <STDIN>;
        if ($debug) {
            print LOG "[match] TOKEN_BAR\n";
        }
        advance();
        skipLinebreaks();
        push @commands, command();
    }
    if ($debug) {
        print LOG "return pipe_sequence()\n";
    }
    return @commands;
}

# command          : simple_command
#                  | compound_command
#                  | compound_command redirect_list
#                  | function_definition
#                  ;
sub command {
    if ($debug) {
        print LOG "command()\n";
    }
    if (match(TOKEN_IF) || match(TOKEN_WHILE)
            || match(TOKEN_UNTIL) || match(TOKEN_FOR)
            || match(TOKEN_CASE) || match(TOKEN_LBRACE)
            || match(TOKEN_LPAREN)) {
        my $compound = compound_command();
        if ($debug) {
            print LOG "return command()\n";
        }
        return $compound;
    }
    else {

        my %tmp_token = %{$token_list[$index + 1]};
        if ($tmp_token{tokenType} == TOKEN_LPAREN) {
            my $ret = function_definition();
            return $ret;
        }
        else {
            my @simple = simple_command();
            if ($debug) {
                print LOG "return command()\n";
            }
            return @simple;
        }
    }
}

# simple_command   : cmd_prefix cmd_word cmd_suffix
#                  | cmd_prefix cmd_word
#                  | cmd_prefix
#                  | cmd_name cmd_suffix
#                  | cmd_name
#                  ;
sub simple_command {
    if ($debug) {
        print LOG "simple_command()\n";
    }
    my $found = 0;
    my @redirects;
    while (!$found) {
        print "\nsuspend in simple_command() + U";
        # my $suspend = <STDIN>;
        if (match(TOKEN_ASSIGNMENT)) {
            if ($debug) {
                print LOG "[match] TOKEN_ASSIGNMENT: ".getText()."\n";
            }
            advance();
        }
        elsif (match(TOKEN_IO_NUMBER) || match(TOKEN_LESS)
                || match(TOKEN_GREAT) || match(TOKEN_DLESS)
                || match(TOKEN_DGREAT) || match(TOKEN_LESSAND)
                || match(TOKEN_GREATAND) || match(TOKEN_LESSGREAT)
                || match(TOKEN_CLOBBER)) {
            if ($debug) {
                print LOG "[goto+u] redirect_list()\n";
            }
            push @redirects, redirect_list();
        }
        else {
            $found = 1;
        }
    }
    if (match(TOKEN_WORD)) {
        my %tmp_token = %{$token_list[$index + 1]};
        if ($tmp_token{tokenType} == TOKEN_LPAREN) {
            return undef;
        }
        if ($debug) {
            print LOG "[match] TOKEN_WORD: ".getText()."\n";
        }
        advance();
        my $loop = 1;
        while ($loop) {
            print "\nsuspend in simple_command() + D";
            # my $suspend = <STDIN>;
            if (match(TOKEN_IO_NUMBER) || match(TOKEN_LESS)
                    || match(TOKEN_GREAT) || match(TOKEN_DLESS)
                    || match(TOKEN_DGREAT) || match(TOKEN_LESSAND)
                    || match(TOKEN_GREATAND) || match(TOKEN_LESSGREAT)
                    || match(TOKEN_CLOBBER)) {
                if ($debug) {
                    print LOG "[goto+d] redirect_list()\n";
                }
                push @redirects, redirect_list();
            }
            elsif (match(TOKEN_WORD) || match(TOKEN_ASSIGNMENT)) {
                my %tmp_token = %{$token_list[$index + 1]};
                if ($tmp_token{tokenType} == TOKEN_LPAREN) {
                    return undef;
                }
                if ($debug) {
                    print LOG "[match] TOKEN_WORD or ASSIGNMENT: ".getText()."\n";
                }
                advance();
            }
            else {
                $loop = 0;
            }
        }
    }
    else {

    }
    if ($debug) {
        print LOG "return simple command()\n";
    }
    return @redirects;
}

# function_definition : fname '(' ')' linebreak function_body
#                  ;
sub function_definition {
    if ($debug) {
        print LOG "function_definition()\n";
    }
    change_type(TOKEN_NAME);
    if (!match(TOKEN_NAME)) {
        if ($debug) {
            print LOG "return function_definintion()\n";
        }
        return undef;
    }
    if ($debug) {
        print LOG "[match] TOKEN_NAME: ".getText()."\n";
    }
    advance();
    if (!match(TOKEN_LPAREN)) {
        back_step();
        if ($debug) {
            print LOG "return function_definintion()\n";
        }
        return undef;
    }
    if ($debug) {
        print LOG "[match] TOKEN_LPAREN\n";
    }
    advance();
    if (!match(TOKEN_RPAREN)) {
        print LOG "Missmatched '(' in function_definintion() got type: ".getType()." text: ".getText()."\n";
        # exception
        if ($debug) {
            print LOG "return function_definintion()\n";
        }
        return undef;
    }
    if ($debug) {
        print LOG "[match] TOKEN_RPAREN\n";
    }
    advance();
    skipLinebreaks();
    function_body();
    if ($debug) {
        print LOG "return function_definintion()\n";
    }
    return undef;
}

# function_body    : compound_command                /* Apply rule 9 */
#                  | compound_command redirect_list  /* Apply rule 9 */
#                  ;
sub function_body {
    if ($debug) {
        print LOG "function_body()\n";
    }
    my @body = compound_command();
    redirect_list_opt();
    if ($debug) {
        print LOG "return function_body()\n";
    }
    return @body;
}

# compound_command : brace_group
#                  | subshell
#                  | for_clause
#                  | case_clause
#                  | if_clause
#                  | while_clause
#                  | until_clause
#                  ;
sub compound_command {
    if ($debug) {
        print LOG "compound_command()\n";
    }
    my $command;
    if (match(TOKEN_IF)) {
        $command = if_clause();
    }
    elsif (match(TOKEN_WHILE)) {
        $command = while_clause();
    }
    elsif (match(TOKEN_UNTIL)) {
        $command = until_clause();
    }
    elsif (match(TOKEN_FOR)) {
        $command = for_clause();
    }
    elsif (match(TOKEN_CASE)) {
        $command = case_clause();
    }
    elsif (match(TOKEN_LBRACE)) {
        $command = brace_group();
    }
    elsif (match(TOKEN_LPAREN)) {
        $command = subshell();
    }
    else {
        die "Unknown in compound_command(), token ".getType(). " text: ".getText()."\n";
        # exception
    }
    $command = redirect_list_opt();
    if ($debug) {
        print LOG "return compound_command()\n";
    }
    return $command;
}

# redirect_list    :               io_redirect
#                  | redirect_list io_redirect
#                  ;
# io_redirect      :           io_file
#                  | IO_NUMBER io_file
#                  |           io_here
#                  | IO_NUMBER io_here
#                  ;
# io_file          : '<'       filename
#                  | LESSAND   filename
#                  | '>'       filename
#                  | GREATAND  filename
#                  | DGREAT    filename
#                  | LESSGREAT filename
#                  | CLOBBER   filename
#                  ;
# io_here          : DLESS     here_end
#                  | DLESSDASH here_end
#                  ;
# redirect_list    : io_redirect redirect_list_R
# redirect_list_R  | io_redirect redirect_list_R
#                  | /* empty */
sub redirect_list {
    if ($debug) {
        print LOG "redirect_list()\n";
    }
    if (match(TOKEN_IO_NUMBER)) {
        if ($debug) {
            print LOG "[match] TOKEN_IO_NUMBER\n";
        }
        advance();
    }
    if (match(TOKEN_LESS) || match(TOKEN_GREAT)
            || match(TOKEN_DGREAT) || match(TOKEN_LESSAND)
            || match(TOKEN_GREATAND) || match(TOKEN_LESSGREAT)
            || match(TOKEN_CLOBBER)) {
        if ($debug) {
            print LOG "[match] *".getType()."\n";
        }
        advance();
        if (!match(TOKEN_WORD)) {
            die "Syntax error in redirect_list()! need TOKEN_WORD, got type: ".getType()." text: ".getText()."\n";
            # exception
        }
        if ($debug) {
            print LOG "[match] TOKEN_WORD: ".getText()."\n";
        }
        advance();
    }
    elsif (match(TOKEN_DLESS) || match(TOKEN_DLESSDASH)) {
        if ($debug) {
            print LOG "[match] *".getType()."\n";
        }
        advance();
        if (!match(TOKEN_WORD)) {
            die "Syntax error in redirect_list()! need TOKEN_WORD, got type: ".getType()." text: ".getText()."\n";
            # exception
        }
        if ($debug) {
            print LOG "[match] TOKEN_WORD: ".getText()."\n";
        }
        advance();
    }
    else {
        die "Syntax error in redirect_list()! unknown TOKEN type: ".getType(). " text: ".getText()."\n"; 
        # exception
    }
    if ($debug) {
        print LOG "return redirect_list()\n";
    }
}

sub redirect_list_opt {
    if ($debug) {
        print LOG "redirect_list_opt\n";
    }
    my @redirects;
    while (1) {
        print "\nsuspend in redirect_list_opt()";
        # my $suspend = <STDIN>;
        if (match(TOKEN_IO_NUMBER) || match(TOKEN_LESS)
                || match(TOKEN_GREAT) || match(TOKEN_DLESS)
                || match(TOKEN_DLESSDASH) || match(TOKEN_DGREAT)
                || match(TOKEN_LESSAND) || match(TOKEN_GREATAND)
                || match(TOKEN_LESSGREAT) || match(TOKEN_CLOBBER)) {
            if ($debug) {
                print LOG "[match] *".getType()."\n";
            }
            if ($debug) {
                print LOG "goto redirect_list()\n";
            }
            push @redirects, redirect_list();
        }
        else {
            last;
        }
    }
    if ($debug) {
        print LOG "return redirect_list_opt()\n";
    }
    if (@redirects) {
        return undef;
    }
    return @redirects;
}

# subshell         : '(' compound_list ')'
#                  ;
sub subshell {
    if ($debug) {
        print LOG "subshell()\n";
    }
    if (!match(TOKEN_LPAREN)) {
        die "Syntax error in subshell()! need '(' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_LPAREN\n";
    }
    advance();
    my @compound_list = compound_list();
    if (!match(TOKEN_RPAREN)) {
        die "Syntax error in subshell()! need ')' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_RPAREN\n";
    }
    advance();
    if ($debug) {
        print LOG "return subshell()\n";
    }
    return @compound_list;
}

# compound_list    :              term
#                  | newline_list term
#                  |              term separator
#                  | newline_list term separator
#                  ;
# term             : term separator and_or
#                  |                and_or
#                  ;
# term             : and_or term_R
# term_R           : separator and_or term_R
#                  | /* empty */
sub compound_list {
    if ($debug) {
        print LOG "compound_list()\n";
    }
    skipLinebreaks();
    my @commands;
    my $command = and_or();
    while (defined($command)) {
        print "\nsuspend in compound_list()";
        # my $suspend = <STDIN>;
        push @commands, $command;
        # skipLinebreaks();
        if (match(TOKEN_NEWLINE)) {
            if ($debug) {
                print LOG "[match] TOKEN_NEWLINE\n";
            }
            skipLinebreaks();
        }
        elsif (match(TOKEN_AMP)) {
            # nothing
            if ($debug) {
                print LOG "[match] TOKEN_AMP\n";
            }
            advance();
        }
        elsif (match(TOKEN_SEMI)) {
            # nothing
            if ($debug) {
                print LOG "[match] TOKEN_SEMI\n";
            }
            advance();
        }
        else {
            last;
        }
        skipLinebreaks();
        $command = and_or_opt();
    }
    if ($debug) {
        print LOG "return compound_list()\n";
    }
}

# brace_group      : Lbrace compound_list Rbrace
#                  ;
sub brace_group {
    if ($debug) {
        print LOG "brace_group()\n";
    }
    if (!match(TOKEN_LBRACE)) {
        die "Syntax error in brace_group()! need '{' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_LBRACE\n";
    }
    advance();
    my @compound_list = compound_list();
    if (!match(TOKEN_RBRACE)) {
        die "Syntax error in brace_group()! need '}' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_RBRACE\n";
    }
    advance();
    if ($debug) {
        print LOG "return brace_group()\n";
    }
    return @compound_list;
}

# case_clause      : Case WORD linebreak in linebreak case_list    Esac
#                  | Case WORD linebreak in linebreak case_list_ns Esac
#                  | Case WORD linebreak in linebreak              Esac
#                  ;
# case_list_ns     : case_list case_item_ns
#                  |           case_item_ns
#                  ;
# case_list        : case_list case_item
#                  |           case_item
#                  ;
sub case_clause {
    if ($debug) {
        print LOG "case_clause()\n";
    }
    my @case_items;
    if (!match(TOKEN_CASE)) {
        die "Syntax error in case_clause()! need 'case' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_CASE\n";
    }
    advance();
    if (!match(TOKEN_WORD)) {
        die "Syntax error in case_clause()! need WORD got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_WORD: ".getText()."\n";
    }
    advance();
    skipLinebreaks();
    if (!match(TOKEN_IN)) {
        die "Syntax error in case_clause()! need 'in' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_IN\n";
    }
    advance();
    skipLinebreaks();
    while (!match(TOKEN_ESAC)) {
        print "\nsuspend in case_clause()";
        # my $suspend = <STDIN>;
        push @case_items, case_item();
        skipLinebreaks();
        if (match(TOKEN_DSEMI)) {
            if ($debug) {
                print LOG "[match] TOKEN_DSEMI\n";
            }
            advance();
            skipLinebreaks();
        }
        elsif (!match(TOKEN_ESAC)) {
            die "Syntax error in case_clause()! need 'esac' got type: ".getType(). " text: ".getText()."\n";
            # exception
        }
        if (match(TOKEN_ESAC)) {
            print LOG "[next] ".getType()." ".getText()."\n";
        }
    }
    advance();
    if ($debug) {
        print LOG "return case_clause()\n";
    }
    return @case_items;
}

# case_item_ns     :     pattern ')'               linebreak
#                  |     pattern ')' compound_list linebreak
#                  | '(' pattern ')'               linebreak
#                  | '(' pattern ')' compound_list linebreak
#                  ;
# case_item        :     pattern ')' linebreak     DSEMI linebreak
#                  |     pattern ')' compound_list DSEMI linebreak
#                  | '(' pattern ')' linebreak     DSEMI linebreak
#                  | '(' pattern ')' compound_list DSEMI linebreak
#                  ;
sub case_item {
    if ($debug) {
        print LOG "case_item()\n";
    }
    if (match(TOKEN_LPAREN)) {
        if ($debug) {
            print LOG "[match] TOKEN_LPAREN\n";
        }
        advance();
    }
    my @patterns = pattern();
    if (!match(TOKEN_RPAREN)) {
        die "Syntax error in case_item()! need ')' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_RPAREN\n";
    }
    advance();
    skipLinebreaks();
    if (!match(TOKEN_DSEMI) && !match(TOKEN_ESAC)) {
        compound_list();
        skipLinebreaks();
    }
    if ($debug) {
        print LOG "return case_item()\n";
    }
    return @patterns;
}

# pattern          :             WORD         /* Apply rule 4 */
#                  | pattern '|' WORD         /* Do not apply rule 4 */
#                  ;
# pattern          : WORD pattern_R
# pattern_R        : '|' WORD pattern_R
#                  | /* empty */
sub pattern {
    if ($debug) {
        print LOG "pattern()\n";
    }
    while (1) {
        print "\nsuspend in pattern()";
        # my $suspend = <STDIN>;
        if (!match(TOKEN_WORD)) {
            die "Syntax error in pattern! need WORD got type: ".getType(). " text: ".getText()."\n";
            # exception
        }
        if ($debug) {
            print LOG "[match] TOKEN_WORD: ".getText()."\n";
        }
        advance();
        if (!match(TOKEN_BAR)) {
            last;
        }
        if ($debug) {
            print LOG "[match] TOKEN_BAR\n";
        }
        advance();
    }
    if ($debug) {
        print LOG "return pattern()\n";
    }
}

# for_clause       : For name linebreak                            do_group
#                  | For name linebreak in          sequential_sep do_group
#                  | For name linebreak in wordlist sequential_sep do_group
#                  ;
# sequential_sep   : ';' linebreak
#                  | newline_list
#                  ;
sub for_clause {
    if ($debug) {
        print LOG "for_clause()\n";
    }
    if (!match(TOKEN_FOR)) {
        die "Syntax error in for_clause()! need 'for' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_FOR\n";
    }
    advance();
    change_type(TOKEN_NAME);
    if (!match(TOKEN_NAME)) {
        die "Syntax error in for_clause()! need NAME got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_NAME: ".getText()."\n";
    }
    advance();
    skipLinebreaks();
    if (match(TOKEN_IN)) {
        if ($debug) {
            print LOG "[match] TOKEN_IN\n";
        }
        advance();
        my $words = 0;
        while (match(TOKEN_WORD)) {
            print "\nsuspend in for_clause()";
            # my $suspend = <STDIN>;
            $words = 1; 
            if ($debug) {
                print LOG "[match] TOKEN_WORD: ".getText()."\n";
            }
            advance();
        }
        if (!$words) {
            die "Syntax error in for_clause(), missing WORD\n"
            # exception
        }
        if (match(TOKEN_SEMI)) {
            if ($debug) {
                print LOG "[match] TOKEN_SEMI\n";
            }
            advance();
            skipLinebreaks();
        }
        elsif (match(TOKEN_NEWLINE)) {
            skipLinebreaks();
        }
        else {
            die "Syntax error in for_clause(), unknown token: ".getType()." text: ".getText()."\n";
            # exception
        }
    }
    my $do_group = do_group();
    if ($debug) {
        print LOG "return for_clause()\n";
    }
    return $do_group;
}

# do_group         : Do compound_list Done           /* Apply rule 6 */
#                  ;
sub do_group {
    if ($debug) {
        print LOG "do_group()\n";
    }
    if (!match(TOKEN_DO)) {
        die "Syntax error in do_group()! need 'do' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_DO\n";
    }
    advance();
    my $compound_list = compound_list();
    if (!match(TOKEN_DONE)) {
        die "Syntax error in do_group()! need 'done' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_DONE\n";
    }
    advance();
    if ($debug) {
        print LOG "return do_group()\n";
    }
    return $compound_list;
}

# until_clause     : Until compound_list do_group
#                  ;
sub until_clause {
    if ($debug) {
        print LOG "until_clause\n";
    }
    if (!match(TOKEN_UNTIL)) {
        die "Syntax error in until_clause()! need 'until' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_UNTIL\n";
    }
    advance();
    my $compound_list = compound_list();
    my $do_group = do_group();
    if ($debug) {
        print LOG "return until_clause()\n";
    }
    return $compound_list.$do_group;
}

# while_clause     : While compound_list do_group
#                  ;
sub while_clause {
    if ($debug) {
        print LOG "while_clause()\n";
    }
    if (!match(TOKEN_WHILE)) {
        die "Syntax error in while_clause()! need 'while' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_WHILE\n";
    }
    advance();
    my $compound_list = compound_list();
    my $do_group = do_group();
    if ($debug) {
        print LOG "return while_clause()\n";
    }
    return $compound_list.$do_group;
}

# if_clause        : If compound_list Then compound_list else_part Fi
#                  | If compound_list Then compound_list           Fi
#                  ;
sub if_clause {
    if ($debug) {
        print LOG "if_clause()\n";
    }
    if (!match(TOKEN_IF)) {
        die "Syntax error in if_clause()! need 'if' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_IF\n";
    }
    advance();
    my @compound_lists;
    push @compound_lists, compound_list();
    if (!match(TOKEN_THEN)) {
        die "Syntax error in if_clause()! need 'then' got type: ".getType(). " text: ".getText()."\n";
        # exception
        
    }
    if ($debug) {
        print LOG "[match] TOKEN_THEN\n";
    }
    advance();
    push @compound_lists, compound_list();
    my $else_part = else_part_opt();
    if (!match(TOKEN_FI)) {
        die "Syntax error in if_clause()! need 'fi' got type: ".getType(). " text: ".getText()."\n";
        # exception
    }
    if ($debug) {
        print LOG "[match] TOKEN_FI\n";
    }
    advance();
    if ($debug) {
        print LOG "return if_clause()\n";
    }
    return @compound_lists;
}

# else_part        : Elif compound_list Then else_part
#                  | Else compound_list
#                  ;h
sub else_part_opt {
    if ($debug) {
        print LOG "else_part_opt()\n";
    }
    if (match(TOKEN_ELIF)) {
        if ($debug) {
            print LOG "[match] TOKEN_ELIF\n";
        }
        advance();
        #if (match(TOKEN_LFANG)) {
        #    if ($debug) {
        #        print LOG "[match] TOKEN_LFANG\n";
        #    }
        #    advance();
        #}
        compound_list();
        #if (match(TOKEN_RFANG)) {
        #    if ($debug) {
        #        print LOG "[match] TOKEN_RFANG\n";
        #    }
        #    advance();
        #}
        if (match(TOKEN_SEMI)) {
            if ($debug) {
                print LOG "[match] TOKEN_SEMI\n";
            }
            advance();
        }
        if (!match(TOKEN_THEN)) {
            die "Syntax error in else_part_opt()! need 'then' got type: ".getType(). " text: ".getText()."\n";
            # exception
        }
        if ($debug) {
            print LOG "[match] TOKEN_THEN\n";
        }
        advance();
        my @compound_lists;
        push @compound_lists, compound_list();
        else_part_opt();
        if ($debug) {
            print LOG "return else_part_opt()\n";
        }
        return @compound_lists;
    }
    elsif (match(TOKEN_ELSE)) {
        if ($debug) {
            print LOG "[match] TOKEN_ELSE\n";
        }
        advance();
        my $compound_list = compound_list();
        if ($debug) {
            print LOG "return else_part_opt()\n";
        }
        return $compound_list;
    }
    else {
        # back_step();
        if ($debug) {
            print LOG "return else_part_opt()\n";
        }
        return undef;
    }
}

get_tokens();
parse();

close(LOG);

